import java.util.concurrent.ThreadLocalRandom;

public class num75 {
    //插入排序
//    public void sortColors(int[] nums) {
//        insertSort(nums);
//        System.out.println(nums);
//    }
//
//    private void insertSort(int[] nums) {
//        for (int i = 1; i < nums.length; i++) {
//            for (int j = i; j >= 1 && nums[j] < nums[j - 1]; j --) {
//                swap(nums,j,j - 1);
//            }
//        }
//    }
//
//    private void swap(int[] nums, int j, int i) {
//        int temp = nums[j];
//        nums[j] = nums[i];
//        nums[i] = temp;
//    }

    //快速排序
    public void sortColors(int[] nums) {
        quickSort(nums,0,nums.length - 1);
    }

    private void quickSort(int[] nums, int l, int r) {
        if(l >= r) {
            return;
        }
       int p = quick(nums,l,r);
        quickSort(nums,l,p - 1);
        quickSort(nums,p + 1,r);
    }

    private int quick(int[] nums, int l, int r) {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        int ran = random.nextInt(l,r);
        swap(nums,l,ran);
        int j = l;
        int val = nums[l];
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] < val) {
                swap(nums,i,j + 1);
                j ++;
            }
        }
        swap(nums,l,j);
        return j;
    }
    private void swap(int[] nums, int j, int i) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
}
